import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;
// https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
public class FindMore {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

        class Solution {

            private  class PII {
                int num;
                int cnt;

                public PII(int num) {
                    this.num = num;
                    cnt = 1;
                }

                public PII(int num, int cnt) {
                    this.num = num;
                    this.cnt = cnt;
                }
            }

            public int[] findMode(TreeNode root) {
                PriorityQueue<PII> queue = new PriorityQueue<>((t1, t2) -> {
                    return t2.cnt - t1.cnt;
                });
                // 中序遍历
                Stack<TreeNode> stack = new Stack<>();
                PII pnode = new PII(-0x3f3f3f3f, -100);
                while (!stack.isEmpty() || root != null) {
                    while (root != null) {
                        stack.push(root);
                        root = root.left;
                    }
                    TreeNode node = stack.pop();
                    if (pnode.num != node.val) {
                        queue.add(pnode);
                        pnode = new PII(node.val);
                    } else {
                        pnode.cnt++;
                    }
                    root = node.right;
                }
                queue.add(pnode);
                List<Integer> lis = new ArrayList<>();
                PII p = queue.poll();
                lis.add(p.num);
                while (!queue.isEmpty()) {
                    PII pi = queue.poll();
                    if (pi.cnt == p.cnt) {
                        lis.add(pi.num);
                    } else {
                        break;
                    }
                }

                int[] res = new int[lis.size()];
                for (int i = 0; i < res.length; i++) {
                    res[i] = lis.get(i);
                }
                return res;

            }


        }

}
